//===--- CastOptimizer.cpp ------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
///
/// \file
///
/// This file contains local cast optimizations and simplifications.
///
//===----------------------------------------------------------------------===//

#include "polarphp/pil/optimizer/utils/CastOptimizer.h"
#include "polarphp/ast/GenericSignature.h"
#include "polarphp/ast/Module.h"
#include "polarphp/ast/SubstitutionMap.h"
#include "polarphp/pil/lang/BasicBlockUtils.h"
#include "polarphp/pil/lang/DebugUtils.h"
#include "polarphp/pil/lang/DynamicCasts.h"
#include "polarphp/pil/lang/InstructionUtils.h"
#include "polarphp/pil/lang/PILArgument.h"
#include "polarphp/pil/lang/PILBuilder.h"
#include "polarphp/pil/lang/PILModule.h"
#include "polarphp/pil/lang/PILUndef.h"
#include "polarphp/pil/optimizer/utils/PILOptFunctionBuilder.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/StringSwitch.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/Support/CommandLine.h"
#include <deque>

using namespace polar;

//===----------------------------------------------------------------------===//
//                  ObjC -> Swift Bridging Cast Optimization
//===----------------------------------------------------------------------===//

static PILFunction *
getObjCToSwiftBridgingFunction(PILOptFunctionBuilder &funcBuilder,
                               PILDynamicCastInst dynamicCast) {
   // inline constructor.
   auto *bridgeFuncDecl = [&]() -> FuncDecl * {
      auto &astContext = dynamicCast.getModule().getAstContext();
      if (dynamicCast.isConditional()) {
         return astContext.getConditionallyBridgeFromObjectiveCBridgeable();
      }
      return astContext.getForceBridgeFromObjectiveCBridgeable();
   }();

   assert(bridgeFuncDecl && "Bridging function doesn't exist?!");

   PILDeclRef funcDeclRef(bridgeFuncDecl, PILDeclRef::Kind::Func);

   // Lookup a function from the stdlib.
   return funcBuilder.getOrCreateFunction(dynamicCast.getLocation(), funcDeclRef,
                                          ForDefinition_t::NotForDefinition);
}

static SubstitutionMap lookupBridgeToObjCInterfaceSubs(PILModule &mod,
                                                       CanType target) {
   auto bridgedProto =
      mod.getAstContext().getInterface(KnownInterfaceKind::ObjectiveCBridgeable);
   auto conf = mod.getPolarphpModule()->lookupConformance(target, bridgedProto);
   return SubstitutionMap::getInterfaceSubstitutions(conf.getRequirement(),
                                                     target, conf);
}

/// Given that our insertion point is at the cast that we are trying to
/// optimize, convert our incoming value to something that can be passed to the
/// bridge call.
// @todo
//static std::pair<PILValue, PILInstruction *>
//convertObjectToLoadableBridgeableType(PILBuilderWithScope &builder,
//                                      PILDynamicCastInst dynamicCast,
//                                      PILValue src) {
//   auto *f = dynamicCast.getFunction();
//   auto loc = dynamicCast.getLocation();
//   bool isConditional = dynamicCast.isConditional();
//
//   PILValue load =
//      builder.emitLoadValueOperation(loc, src, LoadOwnershipQualifier::Take);
//
//   // @todo
////   PILType silBridgedTy = *dynamicCast.getLoweredBridgedTargetObjectType();
//
//   // If we are not conditional...
//   if (!isConditional) {
//      // and our loaded type is our bridged type, just return the load as our
//      // PILValue and signal to our caller that we did not create a new cast
//      // instruction by returning nullptr as second.
////      if (load->getType() == silBridgedTy) {
////         return {load, nullptr};
////      }
//
//      // Otherwise, just perform an unconditional checked cast to the sil bridged
//      // ty. We return the cast as our value and as our new cast instruction.
//      auto *cast =
//         builder.createUnconditionalCheckedCast(loc, load, silBridgedTy,
//                                                dynamicCast.getBridgedTargetType());
//      return {cast, cast};
//   }
//
//   PILBasicBlock *castSuccessBB =
//      f->createBasicBlockAfter(dynamicCast.getInstruction()->getParent());
//   castSuccessBB->createPhiArgument(silBridgedTy, ValueOwnershipKind::Owned);
//
//   // If we /are/ conditional and we do not need to bridge the load to the sil,
//   // then we just create our cast success block and branch from the end of the
//   // cast instruction block to the cast success block. We leave our insertion
//   // point in the cast success block since when we return, we are going to
//   // insert the bridge call/switch there. We return the argument of the cast
//   // success block as the value to be passed to the bridging function.
//   if (load->getType() == silBridgedTy) {
//      castSuccessBB->moveAfter(dynamicCast.getInstruction()->getParent());
//      builder.createBranch(loc, castSuccessBB, load);
//      builder.setInsertionPoint(castSuccessBB);
//      return {castSuccessBB->getArgument(0), nullptr};
//   }
//
//   auto *castFailBB = ([&]() -> PILBasicBlock * {
//      auto *failureBB = dynamicCast.getFailureBlock();
//      PILBuilderWithScope failureBBBuilder(&(*failureBB->begin()), builder);
//      return splitBasicBlockAndBranch(failureBBBuilder, &(*failureBB->begin()),
//                                      nullptr, nullptr);
//   }());
//
//   // Now that we have created the failure bb, move our cast success block right
//   // after the checked_cast_br bb.
//   castSuccessBB->moveAfter(dynamicCast.getInstruction()->getParent());
//
//   // Ok, we need to perform the full cast optimization. This means that we are
//   // going to replace the cast terminator in inst_block with a checked_cast_br.
//   auto *ccbi = builder.createCheckedCastBranch(loc, false, load, silBridgedTy,
//                                                dynamicCast.getBridgedTargetType(),
//                                                castSuccessBB, castFailBB);
//   splitEdge(ccbi, /* EdgeIdx to CastFailBB */ 1);
//
//   // Now that we have split the edge to cast fail bb, add the default argument
//   // for the checked_cast_br. Then we need to handle our error conditions,
//   // namely we destroy on take_always and otherwise store the value back into
//   // the memory location that we took it out of.
//   {
//      auto *newFailureBlock = ccbi->getFailureBB();
//      PILValue defaultArg;
//      if (builder.hasOwnership()) {
//         defaultArg = newFailureBlock->createPhiArgument(
//            load->getType(), ValueOwnershipKind::Owned);
//      } else {
//         defaultArg = ccbi->getOperand();
//      }
//
//      // This block should be properly terminated already due to our method of
//      // splitting the failure block, so we can use begin() safely.
//      PILBuilderWithScope failureBuilder(newFailureBlock->begin());
//
//      switch (dynamicCast.getBridgedConsumptionKind()) {
//         case CastConsumptionKind::TakeAlways:
//            failureBuilder.emitDestroyValueOperation(loc, defaultArg);
//            break;
//         case CastConsumptionKind::TakeOnSuccess:
//         case CastConsumptionKind::CopyOnSuccess:
//            // Without ownership, we do not need to consume the taken value.
//            if (failureBuilder.hasOwnership()) {
//               failureBuilder.emitStoreValueOperation(loc, defaultArg, src,
//                                                      StoreOwnershipQualifier::Init);
//            }
//            break;
//         case CastConsumptionKind::BorrowAlways:
//            llvm_unreachable("this should never occur here");
//      }
//   }
//
//   builder.setInsertionPoint(castSuccessBB);
//   return {castSuccessBB->getArgument(0), ccbi};
//}

/// Create a call of _forceBridgeFromObjectiveC_bridgeable or
/// _conditionallyBridgeFromObjectiveC_bridgeable which converts an ObjC
/// instance into a corresponding Swift type, conforming to
/// _ObjectiveCBridgeable.
///
/// Control Flow Modification Model
/// ===============================
///
/// NOTE: In the following we assume that our src type is not address only. We
/// do not support optimizing such source types today.
///
/// Unconditional Casts
/// -------------------
///
/// In the case of unconditional casts, we do not touch the CFG at all. We
/// perform the following optimizations:
///
/// 1. If the bridged type and the src type equal, we replace the cast with the
///    apply.
///
/// 2. If src is an address and bridged type has the matching object type to
///    src, just load the value and again replace the cast with the apply.
///
/// 3. If src is an address and after loading still doesn't match bridged type,
///    insert an unconditional_checked_cast before calling the apply.
///
/// Conditional Casts
/// -----------------
///
/// In the case of a conditional const (i.e. checked_cast_addr_br), we transform
/// the following CFG:
///
/// ```
///    InstBlock (checked_cast_addr_br) -> FailureBB -> FailureSucc
///        \
///         \----------------------------> SuccessBB -> SuccessSucc
/// ```
///
/// to a CFG of the following form:
///
/// ```
///   InstBlock (checked_cast_br) -> CastFailBB -> FailureBB -> FailureSucc
///        |                                          ^
///        \-> CastSuccessBB (bridge call + switch) --|
///                 |
///                 \-> BridgeSuccessBB -> SuccessBB -> SuccessSucc
/// ```
///
/// NOTE: That if the underlying src type matches the type of the underlying
/// bridge source object, we can omit the initial checked_cast_br and just load
/// the value + branch to the CastSuccessBB. This results instead in the
/// following CFG:
///
/// ```
///   InstBlock (br)                             FailureBB -> FailureSucc
///        |                                          ^
///        \-> CastSuccessBB (bridge call + switch) --|
///                 |
///                 \-> BridgeSuccessBB -> SuccessBB -> SuccessSucc
/// ```
///
//PILInstruction *
//CastOptimizer::optimizeBridgedObjCToSwiftCast(PILDynamicCastInst dynamicCast) {
//   auto kind = dynamicCast.getKind();
//   (void)kind;
//   assert(((kind == PILDynamicCastKind::CheckedCastAddrBranchInst) ||
//           (kind == PILDynamicCastKind::UnconditionalCheckedCastAddrInst)) &&
//          "Unsupported dynamic cast kind");
//
//   CanType target = dynamicCast.getTargetFormalType();
//   auto &mod = dynamicCast.getModule();
//
//   // AnyHashable is a special case that we do not handle since we only handle
//   // objc targets in this function. Bailout early.
//   if (auto dt = target.getNominalOrBoundGenericNominal()) {
//      if (dt == mod.getAstContext().getAnyHashableDecl()) {
//         return nullptr;
//      }
//   }
//
//   PILValue src = dynamicCast.getSource();
//
//   PILInstruction *Inst = dynamicCast.getInstruction();
//   auto *F = Inst->getFunction();
//
//   // Check if we have a source type that is address only. We do not support that
//   // today.
//   if (src->getType().isAddressOnly(*F)) {
//      return nullptr;
//   }
//
//   bool isConditional = dynamicCast.isConditional();
//   PILValue Dest = dynamicCast.getDest();
//   PILBasicBlock *SuccessBB = dynamicCast.getSuccessBlock();
//   PILBasicBlock *FailureBB = dynamicCast.getFailureBlock();
//   auto Loc = Inst->getLoc();
//
//   // The conformance to _BridgedToObjectiveC is statically known.
//   // Retrieve the bridging operation to be used if a static conformance
//   // to _BridgedToObjectiveC can be proven.
//   PILFunction *bridgingFunc =
//      getObjCToSwiftBridgingFunction(functionBuilder, dynamicCast);
//   if (!bridgingFunc)
//      return nullptr;
//
//   auto paramTypes = bridgingFunc->getLoweredFunctionType()->getParameters();
//   (void)paramTypes;
//   assert(paramTypes[0].getConvention() ==
//          ParameterConvention::Direct_Guaranteed &&
//          "Parameter should be @guaranteed");
//
//   PILBuilderWithScope Builder(Inst, builderContext);
//
//   // Generate a load for the source argument since as part of our optimization
//   // we are going to promote the cast to work with objects instead of
//   // addresses. Additionally, if we have an objc object that is not bridgeable,
//   // but that could be converted to something that is bridgeable, we try to
//   // convert to the bridgeable type.
//   PILValue srcOp;
//   PILInstruction *newI;
//   std::tie(srcOp, newI) =
//      convertObjectToLoadableBridgeableType(Builder, dynamicCast, src);
//
//   // Now emit the a cast from the casted ObjC object into a target type.
//   // This is done by means of calling _forceBridgeFromObjectiveC or
//   // _conditionallyBridgeFromObjectiveC_bridgeable from the Target type.
//   auto *funcRef = Builder.createFunctionRefFor(Loc, bridgingFunc);
//   SubstitutionMap subMap = lookupBridgeToObjCInterfaceSubs(mod, target);
//
//   auto MetaTy = MetatypeType::get(target, MetatypeRepresentation::Thick);
//   auto PILMetaTy = F->getTypeLowering(MetaTy).getLoweredType();
//   auto *MetaTyVal = Builder.createMetatype(Loc, PILMetaTy);
//
//   // Temporary to hold the intermediate result.
//   AllocStackInst *Tmp = nullptr;
//   CanType OptionalTy;
//   PILValue outOptionalParam;
//   if (isConditional) {
//      // Create a temporary
//      OptionalTy = OptionalType::get(Dest->getType().getAstType())
//         ->getImplementationType()
//         ->getCanonicalType();
//      Tmp = Builder.createAllocStack(Loc,
//                                     PILType::getPrimitiveObjectType(OptionalTy));
//      outOptionalParam = Tmp;
//   } else {
//      outOptionalParam = Dest;
//   }
//
//   // Emit a retain.
//   PILValue srcArg = Builder.emitCopyValueOperation(Loc, srcOp);
//
//   SmallVector<PILValue, 1> Args;
//   Args.push_back(outOptionalParam);
//   Args.push_back(srcArg);
//   Args.push_back(MetaTyVal);
//
//   auto *AI = Builder.createApply(Loc, funcRef, subMap, Args);
//
//   // If we have guaranteed normal arguments, insert the destroy.
//   //
//   // TODO: Is it safe to just eliminate the initial retain?
//   Builder.emitDestroyOperation(Loc, srcArg);
//
//   // If we have an unconditional_checked_cast_addr, return early. We do not need
//   // to handle any conditional code.
//   if (isa<UnconditionalCheckedCastAddrInst>(Inst)) {
//      // Destroy the source value as unconditional_checked_cast_addr would.
//      Builder.emitDestroyOperation(Loc, srcOp);
//      eraseInstAction(Inst);
//      return (newI) ? newI : AI;
//   }
//
//   auto *CCABI = cast<CheckedCastAddrBranchInst>(Inst);
//   switch (CCABI->getConsumptionKind()) {
//      case CastConsumptionKind::TakeAlways:
//         Builder.emitDestroyOperation(Loc, srcOp);
//         break;
//      case CastConsumptionKind::TakeOnSuccess: {
//         {
//            // Insert a release in the success BB.
//            PILBuilderWithScope successBuilder(SuccessBB->begin());
//            successBuilder.emitDestroyOperation(Loc, srcOp);
//         }
//         {
//            // And a store in the failure BB.
//            if (Builder.hasOwnership()) {
//               PILBuilderWithScope failureBuilder(FailureBB->begin());
//               PILValue writeback = srcOp;
//               PILType srcType = src->getType().getObjectType();
//               if (writeback->getType() != srcType) {
//                  writeback =
//                     failureBuilder.createUncheckedRefCast(Loc, writeback, srcType);
//               }
//               failureBuilder.emitStoreValueOperation(Loc, writeback, src,
//                                                      StoreOwnershipQualifier::Init);
//            }
//         }
//         break;
//      }
//      case CastConsumptionKind::BorrowAlways:
//         llvm_unreachable("checked_cast_addr_br never has BorrowAlways");
//      case CastConsumptionKind::CopyOnSuccess:
//         // If we are performing copy_on_success, store the value back into memory
//         // here since we loaded it. We may need to cast back to the actual
//         // underlying type.
//         if (Builder.hasOwnership()) {
//            PILValue writeback = srcOp;
//            PILType srcType = src->getType().getObjectType();
//            if (writeback->getType() != srcType) {
//               writeback = Builder.createUncheckedRefCast(Loc, writeback, srcType);
//            }
//            Builder.emitStoreValueOperation(Loc, writeback, src,
//                                            StoreOwnershipQualifier::Init);
//         }
//         break;
//   }
//
//   // Results should be checked in case we process a conditional
//   // case. E.g. casts from NSArray into [SwiftType] may fail, i.e. return .None.
//   if (isConditional) {
//      // Copy the temporary into Dest.
//      // Load from the optional.
//      auto *SomeDecl = Builder.getAstContext().getOptionalSomeDecl();
//
//      auto *BridgeSuccessBB =
//         Inst->getFunction()->createBasicBlockAfter(Builder.getInsertionBB());
//      SmallVector<std::pair<EnumElementDecl *, PILBasicBlock *>, 2> CaseBBs;
//      CaseBBs.emplace_back(SomeDecl, BridgeSuccessBB);
//      CaseBBs.emplace_back(mod.getAstContext().getOptionalNoneDecl(), FailureBB);
//
//      Builder.createSwitchEnumAddr(Loc, outOptionalParam, nullptr, CaseBBs);
//
//      Builder.setInsertionPoint(FailureBB->begin());
//      Builder.createDeallocStack(Loc, Tmp);
//
//      Builder.setInsertionPoint(BridgeSuccessBB);
//      auto Addr = Builder.createUncheckedTakeEnumDataAddr(Loc, outOptionalParam,
//                                                          SomeDecl);
//
//      Builder.createCopyAddr(Loc, Addr, Dest, IsTake, IsInitialization);
//
//      Builder.createDeallocStack(Loc, Tmp);
//      SmallVector<PILValue, 1> SuccessBBArgs;
//      Builder.createBranch(Loc, SuccessBB, SuccessBBArgs);
//   }
//
//   eraseInstAction(Inst);
//   return (newI) ? newI : AI;
//}

//===----------------------------------------------------------------------===//
//                  Swift -> ObjC Bridging Cast Optimization
//===----------------------------------------------------------------------===//
//
//static bool canOptimizeCast(const polar::Type &BridgedTargetTy,
//                            polar::PILModule &M,
//                            polar::PILFunctionConventions &substConv) {
//   // DestTy is the type which we want to convert to
//   PILType DestTy =
//      PILType::getPrimitiveObjectType(BridgedTargetTy->getCanonicalType());
//   // ConvTy  is the return type of the _bridgeToObjectiveCImpl()
//   auto ConvTy = substConv.getPILResultType().getObjectType();
//   if (ConvTy == DestTy) {
//      // Destination is the same type
//      return true;
//   }
//   // Check if a superclass/subclass of the source operand
//   if (DestTy.isExactSuperclassOf(ConvTy)) {
//      return true;
//   }
//   if (ConvTy.isExactSuperclassOf(DestTy)) {
//      return true;
//   }
//   // check if it is a bridgeable CF type
//   if (ConvTy.getAstType() ==
//       getNSBridgedClassOfCFClass(M.getPolarphpModule(),
//                                  DestTy.getAstType())) {
//      return true;
//   }
//   if (DestTy.getAstType() ==
//       getNSBridgedClassOfCFClass(M.getPolarphpModule(),
//                                  ConvTy.getAstType())) {
//      return true;
//   }
//   // All else failed - can't optimize this case
//   return false;
//}
//
//static Optional<std::pair<PILFunction *, SubstitutionMap>>
//findBridgeToObjCFunc(PILOptFunctionBuilder &functionBuilder,
//                     PILDynamicCastInst dynamicCast) {
//   CanType sourceFormalType = dynamicCast.getSourceFormalType();
//   auto loc = dynamicCast.getLocation();
//   auto &mod = dynamicCast.getModule();
//   auto bridgedProto =
//      mod.getAstContext().getInterface(KnownInterfaceKind::ObjectiveCBridgeable);
//
//   auto conf = mod.getPolarphpModule()->lookupConformance(
//      sourceFormalType, bridgedProto);
//   assert(conf && "_ObjectiveCBridgeable conformance should exist");
//   (void)conf;
//
//   // Generate code to invoke _bridgeToObjectiveC
//   ModuleDecl *modDecl =
//      mod.getAstContext().getLoadedModule(mod.getAstContext().Id_Foundation);
//   if (!modDecl)
//      return None;
//   SmallVector<ValueDecl *, 2> results;
//   modDecl->lookupMember(results,
//                         sourceFormalType.getNominalOrBoundGenericNominal(),
//                         mod.getAstContext().Id_bridgeToObjectiveC,
//                         Identifier());
//   ArrayRef<ValueDecl *> resultsRef(results);
//   if (resultsRef.empty()) {
//      mod.getPolarphpModule()->lookupMember(
//         results, sourceFormalType.getNominalOrBoundGenericNominal(),
//         mod.getAstContext().Id_bridgeToObjectiveC, Identifier());
//      resultsRef = results;
//   }
//   if (resultsRef.size() != 1)
//      return None;
//
//   auto *resultDecl = results.front();
//   auto memberDeclRef = PILDeclRef(resultDecl);
//   auto *bridgedFunc = functionBuilder.getOrCreateFunction(
//      loc, memberDeclRef, ForDefinition_t::NotForDefinition);
//
//   // Get substitutions, if source is a bound generic type.
//   auto subMap = sourceFormalType->getContextSubstitutionMap(
//      mod.getPolarphpModule(), resultDecl->getDeclContext());
//
//   // Implementation of _bridgeToObjectiveC could not be found.
//   if (!bridgedFunc)
//      return None;
//
//   if (dynamicCast.getFunction()->isSerialized() &&
//       !bridgedFunc->hasValidLinkageForFragileRef())
//      return None;
//
//   if (bridgedFunc->getLoweredFunctionType()
//      ->getSingleResult()
//      .isFormalIndirect())
//      return None;
//   return std::make_pair(bridgedFunc, subMap);
//}

//static PILValue computeFinalCastedValue(PILBuilderWithScope &builder,
//                                        PILDynamicCastInst dynamicCast,
//                                        ApplyInst *newAI) {
//   auto loc = dynamicCast.getLocation();
//   auto convTy = newAI->getType();
//   bool isConditional = dynamicCast.isConditional();
//   auto destLoweredTy = dynamicCast.getTargetLoweredType().getObjectType();
//   auto destFormalTy = dynamicCast.getTargetFormalType();
//   assert(destLoweredTy == dynamicCast.getLoweredBridgedTargetObjectType() &&
//          "Expected Dest Type to be the same as BridgedTargetTy");
//
//   auto &m = dynamicCast.getModule();
//   if (convTy == destLoweredTy) {
//      return newAI;
//   }
//
//   if (destLoweredTy.isExactSuperclassOf(convTy)) {
//      return builder.createUpcast(loc, newAI, destLoweredTy);
//   }
//
//   if (convTy.isExactSuperclassOf(destLoweredTy)) {
//      // If we are not conditional, we are ok with the downcast via checked cast
//      // fails since we will trap.
//      if (!isConditional) {
//         return builder.createUnconditionalCheckedCast(loc, newAI,
//                                                       destLoweredTy, destFormalTy);
//      }
//
//      // Otherwise if we /are/ emitting a conditional cast, make sure that we
//      // handle the failure gracefully.
//      //
//      // Since we are being returned the value at +1, we need to destroy the
//      // newAI on failure.
//      auto *failureBB = dynamicCast.getFailureBlock();
//      {
//         PILBuilderWithScope innerBuilder(&*failureBB->begin(), builder);
//         auto valueToDestroy = ([&]() -> PILValue {
//            if (!innerBuilder.hasOwnership())
//               return newAI;
//            return failureBB->createPhiArgument(newAI->getType(),
//                                                ValueOwnershipKind::Owned);
//         }());
//         innerBuilder.emitDestroyOperation(loc, valueToDestroy);
//      }
//
//      auto *condBrSuccessBB =
//         newAI->getFunction()->createBasicBlockAfter(newAI->getParent());
//      condBrSuccessBB->createPhiArgument(destLoweredTy, ValueOwnershipKind::Owned);
//      builder.createCheckedCastBranch(loc, /* isExact*/ false, newAI,
//                                      destLoweredTy, destFormalTy,
//                                      condBrSuccessBB, failureBB);
//      builder.setInsertionPoint(condBrSuccessBB, condBrSuccessBB->begin());
//      return condBrSuccessBB->getArgument(0);
//   }
//
//   if (convTy.getAstType() ==
//       getNSBridgedClassOfCFClass(m.getPolarphpModule(), destLoweredTy.getAstType()) ||
//       destLoweredTy.getAstType() ==
//       getNSBridgedClassOfCFClass(m.getPolarphpModule(), convTy.getAstType())) {
//      // Handle NS <-> CF toll-free bridging here.
//      return PILValue(builder.createUncheckedRefCast(loc, newAI, destLoweredTy));
//   }
//
//   llvm_unreachable(
//      "optimizeBridgedSwiftToObjCCast: should never reach this condition: if "
//      "the Destination does not have the same type, is not a bridgeable CF "
//      "type and isn't a superclass/subclass of the source operand we should "
//      "have bailed earlier.");
//}

/// Create a call of _bridgeToObjectiveC which converts an _ObjectiveCBridgeable
/// instance into a bridged ObjC type.
//PILInstruction *
//CastOptimizer::optimizeBridgedSwiftToObjCCast(PILDynamicCastInst dynamicCast) {
//   PILInstruction *Inst = dynamicCast.getInstruction();
//   const PILFunction *F = Inst->getFunction();
//   CastConsumptionKind ConsumptionKind = dynamicCast.getBridgedConsumptionKind();
//   bool isConditional = dynamicCast.isConditional();
//   PILValue Src = dynamicCast.getSource();
//   PILValue Dest = dynamicCast.getDest();
//   CanType BridgedTargetTy = dynamicCast.getBridgedTargetType();
//   PILBasicBlock *SuccessBB = dynamicCast.getSuccessBlock();
//   PILBasicBlock *FailureBB = dynamicCast.getFailureBlock();
//   auto &M = Inst->getModule();
//   auto Loc = Inst->getLoc();
//
//   bool AddressOnlyType = false;
//   if (!Src->getType().isLoadable(*F) || !Dest->getType().isLoadable(*F)) {
//      AddressOnlyType = true;
//   }
//
//   // Find the _BridgedToObjectiveC protocol.
//   PILFunction *bridgedFunc = nullptr;
//   SubstitutionMap subMap;
//   {
//      auto result = findBridgeToObjCFunc(functionBuilder, dynamicCast);
//      if (!result)
//         return nullptr;
//      std::tie(bridgedFunc, subMap) = result.getValue();
//   }
//
//   PILType SubstFnTy = bridgedFunc->getLoweredType().substGenericArgs(
//      M, subMap, TypeExpansionContext(*F));
//   PILFunctionConventions substConv(SubstFnTy.castTo<PILFunctionType>(), M);
//
//   // Check that this is a case that the authors of this code thought it could
//   // handle.
//   if (!canOptimizeCast(BridgedTargetTy, M, substConv)) {
//      return nullptr;
//   }
//
//   PILBuilderWithScope Builder(Inst, builderContext);
//   auto FnRef = Builder.createFunctionRefFor(Loc, bridgedFunc);
//   auto ParamTypes = SubstFnTy.castTo<PILFunctionType>()->getParameters();
//   PILValue oldSrc;
//   if (Src->getType().isAddress() && !substConv.isPILIndirect(ParamTypes[0])) {
//      // Create load
//      oldSrc = Src;
//      Src =
//         Builder.emitLoadValueOperation(Loc, Src, LoadOwnershipQualifier::Take);
//   }
//
//   // Compensate different owning conventions of the replaced cast instruction
//   // and the inserted conversion function.
//   bool needReleaseAfterCall = false;
//   bool needReleaseInSuccess = false;
//   switch (ParamTypes[0].getConvention()) {
//      case ParameterConvention::Direct_Guaranteed:
//      case ParameterConvention::Indirect_In_Guaranteed:
//         switch (ConsumptionKind) {
//            case CastConsumptionKind::TakeAlways:
//               needReleaseAfterCall = true;
//               break;
//            case CastConsumptionKind::TakeOnSuccess:
//               needReleaseInSuccess = true;
//               break;
//            case CastConsumptionKind::BorrowAlways:
//               llvm_unreachable("Should never hit this");
//            case CastConsumptionKind::CopyOnSuccess:
//               // We assume that our caller is correct and will treat our argument as
//               // being immutable, so we do not need to do anything here.
//               break;
//         }
//         break;
//      case ParameterConvention::Direct_Owned:
//      case ParameterConvention::Indirect_In:
//      case ParameterConvention::Indirect_In_Constant:
//         // Currently this
//         // cannot appear, because the _bridgeToObjectiveC protocol witness method
//         // always receives the this pointer (= the source) as guaranteed.
//         // If it became possible (perhaps with the advent of ownership and
//         // explicit +1 annotations), the implementation should look something
//         // like this:
//         /*
//         switch (ConsumptionKind) {
//           case CastConsumptionKind::TakeAlways:
//             break;
//           case CastConsumptionKind::TakeOnSuccess:
//             needRetainBeforeCall = true;
//             needReleaseInSuccess = true;
//             break;
//           case CastConsumptionKind::CopyOnSuccess:
//             needRetainBeforeCall = true;
//             break;
//         }
//         break;
//          */
//         llvm_unreachable("this should never happen so is currently untestable");
//      case ParameterConvention::Direct_Unowned:
//         assert(!AddressOnlyType &&
//                "AddressOnlyType with Direct_Unowned is not supported");
//         break;
//      case ParameterConvention::Indirect_Inout:
//      case ParameterConvention::Indirect_InoutAliasable:
//         // TODO handle remaining indirect argument types
//         return nullptr;
//   }
//
//   // Generate a code to invoke the bridging function.
//   auto *NewAI = Builder.createApply(Loc, FnRef, subMap, Src);
//
//   // First if we are going to destroy the value unconditionally, just insert the
//   // destroy right after the call. This handles some of the conditional cases
//   // and /all/ of the consuming unconditional cases.
//   if (needReleaseAfterCall) {
//      Builder.emitDestroyOperation(Loc, Src);
//   } else {
//      if (SuccessBB) {
//         PILBuilderWithScope succBuilder(&*SuccessBB->begin(), Builder);
//         if (needReleaseInSuccess) {
//            succBuilder.emitDestroyOperation(Loc, Src);
//         } else {
//            if (oldSrc) {
//               succBuilder.emitStoreValueOperation(Loc, Src, oldSrc,
//                                                   StoreOwnershipQualifier::Init);
//            }
//         }
//         PILBuilderWithScope failBuilder(&*FailureBB->begin(), Builder);
//         if (oldSrc) {
//            failBuilder.emitStoreValueOperation(Loc, Src, oldSrc,
//                                                StoreOwnershipQualifier::Init);
//         }
//      } else {
//         if (oldSrc) {
//            Builder.emitStoreValueOperation(Loc, Src, oldSrc,
//                                            StoreOwnershipQualifier::Init);
//         }
//      }
//   }
//
//   if (!Dest)
//      return NewAI;
//
//   // If it is addr cast then store the result into the dest.
//   //
//   // NOTE: We assume that dest was uninitialized when passed to us.
//   PILValue castedValue = computeFinalCastedValue(Builder, dynamicCast, NewAI);
//   auto qual = Builder.hasOwnership() ? StoreOwnershipQualifier::Init
//                                      : StoreOwnershipQualifier::Unqualified;
//   PILInstruction *NewI = Builder.createStore(Loc, castedValue, Dest, qual);
//   if (isConditional && NewI->getParent() != NewAI->getParent()) {
//      Builder.createBranch(Loc, SuccessBB);
//   }
//
//   eraseInstAction(Inst);
//   return NewI;
//}

//===----------------------------------------------------------------------===//
//               Top Level Bridge Cast Optimization Entrypoint
//===----------------------------------------------------------------------===//

/// Make use of the fact that some of these casts cannot fail.  For
/// example, if the ObjC type is exactly the expected _ObjectiveCType
/// type, then it would always succeed for NSString, NSNumber, etc.
/// Casts from NSArray, NSDictionary and NSSet may fail.
///
/// If ObjC class is not exactly _ObjectiveCType, then its conversion
/// to a required _ObjectiveCType may fail.
//PILInstruction *
//CastOptimizer::optimizeBridgedCasts(PILDynamicCastInst dynamicCast) {
//   CanType source = dynamicCast.getSourceFormalType();
//   CanType target = dynamicCast.getTargetFormalType();
//   auto &M = dynamicCast.getModule();
//
//   // To apply the bridged optimizations, we should ensure that types are not
//   // existential (and keep in mind that generic parameters can be existentials),
//   // and that one of the types is a class and another one is a struct.
//   if (source.isAnyExistentialType() || target.isAnyExistentialType() ||
//       source->is<ArchetypeType>() || target->is<ArchetypeType>() ||
//       (source.getClassOrBoundGenericClass() &&
//        !target.getStructOrBoundGenericStruct()) ||
//       (target.getClassOrBoundGenericClass() &&
//        !source.getStructOrBoundGenericStruct()))
//      return nullptr;
//
//   // Casts involving non-bound generic types cannot be optimized.
//   if (source->hasArchetype() || target->hasArchetype())
//      return nullptr;
//
//
////   CanType CanBridgedSourceTy = dynamicCast.getBridgedSourceType();
////   CanType CanBridgedTargetTy = dynamicCast.getBridgedTargetType();
//
//   // If we were unable to bridge either of our source/target types, return
//   // nullptr.
//   if (!CanBridgedSourceTy || !CanBridgedTargetTy)
//      return nullptr;
//
//   if (CanBridgedSourceTy == source && CanBridgedTargetTy == target) {
//      // Both source and target type are ObjC types.
//      return nullptr;
//   }
//
//   if (CanBridgedSourceTy != source && CanBridgedTargetTy != target) {
//      // Both source and target type are Swift types.
//      return nullptr;
//   }
//
//   if ((CanBridgedSourceTy && CanBridgedSourceTy->getAnyNominal() ==
//                              M.getAstContext().getNSErrorDecl()) ||
//       (CanBridgedTargetTy && CanBridgedTargetTy->getAnyNominal() ==
//                              M.getAstContext().getNSErrorDecl())) {
//      // FIXME: Can't optimize bridging with NSError.
//      return nullptr;
//   }
//
//   // Check what kind of conversion it is? ObjC->Swift or Swift-ObjC?
//   if (CanBridgedTargetTy != target) {
//      // This is an ObjC to Swift cast.
//      return optimizeBridgedObjCToSwiftCast(dynamicCast);
//   } else {
//      // This is a Swift to ObjC cast
//      return optimizeBridgedSwiftToObjCCast(dynamicCast);
//   }
//
//   llvm_unreachable("Unknown kind of bridging");
//}

//===----------------------------------------------------------------------===//
//                         Cast Optimizer Public API
//===----------------------------------------------------------------------===//

PILInstruction *CastOptimizer::simplifyCheckedCastAddrBranchInst(
   CheckedCastAddrBranchInst *Inst) {
   if (auto *I = optimizeCheckedCastAddrBranchInst(Inst))
      Inst = dyn_cast<CheckedCastAddrBranchInst>(I);

   if (!Inst)
      return nullptr;

   PILDynamicCastInst dynamicCast(Inst);
   auto Loc = dynamicCast.getLocation();
   auto Src = dynamicCast.getSource();
   auto Dest = dynamicCast.getDest();
   auto *SuccessBB = dynamicCast.getSuccessBlock();
   auto *FailureBB = dynamicCast.getFailureBlock();

   PILBuilderWithScope Builder(Inst, builderContext);

   // Check if we can statically predict the outcome of the cast.
   auto Feasibility =
      dynamicCast.classifyFeasibility(true /*allow whole module*/);

   if (Feasibility == DynamicCastFeasibility::WillFail) {
      if (shouldDestroyOnFailure(Inst->getConsumptionKind())) {
         auto &srcTL = Builder.getTypeLowering(Src->getType());
         srcTL.emitDestroyAddress(Builder, Loc, Src);
      }
      auto NewI = Builder.createBranch(Loc, FailureBB);
      eraseInstAction(Inst);
      willFailAction();
      return NewI;
   }

   bool ResultNotUsed = isa<AllocStackInst>(Dest);
   if (ResultNotUsed) {
      for (auto Use : Dest->getUses()) {
         auto *User = Use->getUser();
         if (isa<DeallocStackInst>(User) || User == Inst)
            continue;
         ResultNotUsed = false;
         break;
      }
   }

   auto *BB = Inst->getParent();

   PILInstruction *BridgedI = nullptr;

   // To apply the bridged optimizations, we should
   // ensure that types are not existential,
   // and that not both types are classes.
   BridgedI = optimizeBridgedCasts(dynamicCast);

   if (!BridgedI) {
      // If the cast may succeed or fail, and it can't be optimized into a
      // bridging operation, then let it be.
      if (Feasibility == DynamicCastFeasibility::MaySucceed) {
         return nullptr;
      }

      assert(Feasibility == DynamicCastFeasibility::WillSucceed);

      // Replace by unconditional_addr_cast, followed by a branch.
      // The unconditional_addr_cast can be skipped, if the result of a cast
      // is not used afterwards.
      if (ResultNotUsed) {
         if (shouldTakeOnSuccess(Inst->getConsumptionKind())) {
            auto &srcTL = Builder.getTypeLowering(Src->getType());
            srcTL.emitDestroyAddress(Builder, Loc, Src);
         }
         eraseInstAction(Inst);
         Builder.setInsertionPoint(BB);
         auto *NewI = Builder.createBranch(Loc, SuccessBB);
         willSucceedAction();
         return NewI;
      }

      // Since it is an addr cast, only address types are handled here.
      if (!Src->getType().isAddress() || !Dest->getType().isAddress()) {
         return nullptr;
      }

      // For CopyOnSuccess casts, we could insert an explicit copy here, but this
      // case does not happen in practice.
      //
      // Both TakeOnSuccess and TakeAlways can be reduced to an
      // UnconditionalCheckedCast, since the failure path is irrelevant.
      switch (Inst->getConsumptionKind()) {
         case CastConsumptionKind::BorrowAlways:
            llvm_unreachable("checked_cast_addr_br never has BorrowAlways");
         case CastConsumptionKind::CopyOnSuccess:
            return nullptr;
         case CastConsumptionKind::TakeAlways:
         case CastConsumptionKind::TakeOnSuccess:
            break;
      }

      if (!emitSuccessfulIndirectUnconditionalCast(Builder, Loc, dynamicCast)) {
         // No optimization was possible.
         return nullptr;
      }
      eraseInstAction(Inst);
   }
   PILInstruction *NewI = &BB->back();
   if (!isa<TermInst>(NewI)) {
      Builder.setInsertionPoint(BB);
      NewI = Builder.createBranch(Loc, SuccessBB);
   }
   willSucceedAction();
   return NewI;
}

PILInstruction *
CastOptimizer::simplifyCheckedCastBranchInst(CheckedCastBranchInst *Inst) {
   if (Inst->isExact()) {
      PILDynamicCastInst dynamicCast(Inst);
      auto *ARI = dyn_cast<AllocRefInst>(stripUpCasts(dynamicCast.getSource()));
      if (!ARI)
         return nullptr;

      // We know the dynamic type of the operand.
      PILBuilderWithScope Builder(Inst, builderContext);
      auto Loc = dynamicCast.getLocation();

      if (ARI->getType() == dynamicCast.getTargetLoweredType()) {
         // This exact cast will succeed.
         SmallVector<PILValue, 1> Args;
         Args.push_back(ARI);
         auto *NewI =
            Builder.createBranch(Loc, dynamicCast.getSuccessBlock(), Args);
         eraseInstAction(Inst);
         willSucceedAction();
         return NewI;
      }

      // This exact cast will fail. With ownership enabled, we pass a copy of the
      // original casts value to the failure block.
      TinyPtrVector<PILValue> Args;
      if (Builder.hasOwnership())
         Args.push_back(dynamicCast.getSource());
      auto *NewI = Builder.createBranch(Loc, dynamicCast.getFailureBlock(), Args);
      eraseInstAction(Inst);
      willFailAction();
      return NewI;
   }

   if (auto *I = optimizeCheckedCastBranchInst(Inst))
      Inst = dyn_cast<CheckedCastBranchInst>(I);

   if (!Inst)
      return nullptr;

   PILDynamicCastInst dynamicCast(Inst);
   auto TargetLoweredType = dynamicCast.getTargetLoweredType();
   auto TargetFormalType = dynamicCast.getTargetFormalType();
   auto Loc = dynamicCast.getLocation();
   auto *SuccessBB = dynamicCast.getSuccessBlock();
   auto Op = dynamicCast.getSource();
   auto *F = dynamicCast.getFunction();

   // Check if we can statically predict the outcome of the cast.
   auto Feasibility =
      dynamicCast.classifyFeasibility(false /*allow whole module*/);
   if (Feasibility == DynamicCastFeasibility::MaySucceed) {
      return nullptr;
   }

   PILBuilderWithScope Builder(Inst, builderContext);
   if (Feasibility == DynamicCastFeasibility::WillFail) {
      TinyPtrVector<PILValue> Args;
      if (Builder.hasOwnership())
         Args.push_back(Inst->getOperand());
      auto *NewI = Builder.createBranch(Loc, dynamicCast.getFailureBlock(), Args);
      eraseInstAction(Inst);
      willFailAction();
      return NewI;
   }

   assert(Feasibility == DynamicCastFeasibility::WillSucceed);

   bool ResultNotUsed = SuccessBB->getArgument(0)->use_empty();
   PILValue CastedValue;
   if (Op->getType() != TargetLoweredType) {
      // Apply the bridged cast optimizations.
      //
      // TODO: Bridged casts cannot be expressed by checked_cast_br yet.
      // Should we ever support it, please review this code.
      auto BridgedI = optimizeBridgedCasts(dynamicCast);

      if (BridgedI) {
         llvm_unreachable(
            "Bridged casts cannot be expressed by checked_cast_br yet");
      } else {
         // Replace by unconditional_cast, followed by a branch.
         // The unconditional_cast can be skipped, if the result of a cast
         // is not used afterwards.
         if (!ResultNotUsed) {
            if (!dynamicCast.canUseScalarCheckedCastInstructions())
               return nullptr;

            CastedValue =
               emitSuccessfulScalarUnconditionalCast(Builder, Loc, dynamicCast);
         } else {
            CastedValue = PILUndef::get(TargetLoweredType, *F);
         }
         if (!CastedValue)
            CastedValue =
               Builder.createUnconditionalCheckedCast(
                  Loc, Op, TargetLoweredType, TargetFormalType);
      }

   } else {
      // No need to cast.
      CastedValue = Op;
   }

   auto *NewI = Builder.createBranch(Loc, SuccessBB, CastedValue);
   eraseInstAction(Inst);
   willSucceedAction();
   return NewI;
}

PILInstruction *CastOptimizer::simplifyCheckedCastValueBranchInst(
   CheckedCastValueBranchInst *Inst) {
   if (auto *I = optimizeCheckedCastValueBranchInst(Inst))
      Inst = dyn_cast<CheckedCastValueBranchInst>(I);

   if (!Inst)
      return nullptr;

   PILDynamicCastInst dynamicCast(Inst);
   auto SourceFormalType = dynamicCast.getSourceFormalType();
   auto TargetLoweredType = dynamicCast.getTargetLoweredType();
   auto TargetFormalType = dynamicCast.getTargetFormalType();
   auto Loc = dynamicCast.getLocation();
   auto *SuccessBB = dynamicCast.getSuccessBlock();
   auto *FailureBB = dynamicCast.getFailureBlock();
   auto Op = dynamicCast.getSource();
   auto *F = dynamicCast.getFunction();

   // Check if we can statically predict the outcome of the cast.
   auto Feasibility = dynamicCast.classifyFeasibility(false /*allow wmo opts*/);

   PILBuilderWithScope Builder(Inst, builderContext);

   if (Feasibility == DynamicCastFeasibility::WillFail) {
      auto *NewI = Builder.createBranch(Loc, FailureBB);
      eraseInstAction(Inst);
      willFailAction();
      return NewI;
   }

   // Casting will succeed.

   bool ResultNotUsed = SuccessBB->getArgument(0)->use_empty();
   PILValue CastedValue;
   if (Op->getType() != TargetLoweredType) {
      // Apply the bridged cast optimizations.
      // TODO: Bridged casts cannot be expressed by checked_cast_value_br yet.
      // Once the support for opaque values has landed, please review this
      // code.
      auto *BridgedI = optimizeBridgedCasts(dynamicCast);
      if (BridgedI) {
         llvm_unreachable(
            "Bridged casts cannot be expressed by checked_cast_value_br yet");
      } else {
         // If the cast may succeed or fail and can't be turned into a bridging
         // call, then let it be.
         if (Feasibility == DynamicCastFeasibility::MaySucceed) {
            return nullptr;
         }

         assert(Feasibility == DynamicCastFeasibility::WillSucceed);

         // Replace by unconditional_cast, followed by a branch.
         // The unconditional_cast can be skipped, if the result of a cast
         // is not used afterwards.

         if (!dynamicCast.canUseScalarCheckedCastInstructions())
            return nullptr;

         if (!ResultNotUsed) {
            CastedValue =
               emitSuccessfulScalarUnconditionalCast(Builder, Loc, dynamicCast);
         } else {
            CastedValue = PILUndef::get(TargetLoweredType, *F);
         }
      }
      if (!CastedValue)
         CastedValue = Builder.createUnconditionalCheckedCastValue(
            Loc, Op, SourceFormalType,
            TargetLoweredType, TargetFormalType);
   } else {
      // No need to cast.
      CastedValue = Op;
   }

   auto *NewI = Builder.createBranch(Loc, SuccessBB, CastedValue);
   eraseInstAction(Inst);
   willSucceedAction();
   return NewI;
}

PILInstruction *CastOptimizer::optimizeCheckedCastAddrBranchInst(
   CheckedCastAddrBranchInst *Inst) {
   auto Loc = Inst->getLoc();
   auto Src = Inst->getSrc();
   auto Dest = Inst->getDest();
   auto *SuccessBB = Inst->getSuccessBB();
   auto *FailureBB = Inst->getFailureBB();

   // If there is an unbound generic type involved in the cast, bail.
   if (Src->getType().hasArchetype() || Dest->getType().hasArchetype())
      return nullptr;

   // %1 = metatype $A.Type
   // [%2 = init_existential_metatype %1 ...]
   // %3 = alloc_stack
   // store %1 to %3 or store %2 to %3
   // checked_cast_addr_br %3 to ...
   // ->
   // %1 = metatype $A.Type
   // %c = checked_cast_br %1 to ...
   // store %c to %3 (if successful)
   if (auto *ASI = dyn_cast<AllocStackInst>(Src)) {
      // Check if the value of this alloc_stack is set only once by a store
      // instruction, used only by CCABI and then deallocated.
      bool isLegal = true;
      StoreInst *Store = nullptr;
      for (auto Use : ASI->getUses()) {
         auto *User = Use->getUser();
         if (isa<DeallocStackInst>(User) || User == Inst)
            continue;
         if (auto *SI = dyn_cast<StoreInst>(User)) {
            if (!Store) {
               Store = SI;
               continue;
            }
         }
         isLegal = false;
         break;
      }

      if (isLegal && Store) {
         // Check what was the value stored in the allocated stack slot.
         auto Src = Store->getSrc();
         MetatypeInst *MI = nullptr;
         if (auto *IEMI = dyn_cast<InitExistentialMetatypeInst>(Src)) {
            MI = dyn_cast<MetatypeInst>(IEMI->getOperand());
         }

         if (!MI)
            MI = dyn_cast<MetatypeInst>(Src);

         if (MI) {
            if (SuccessBB->getSinglePredecessorBlock() &&
                canUseScalarCheckedCastInstructions(
                   Inst->getModule(), MI->getType().getAstType(),
                   Inst->getTargetFormalType())) {
               PILBuilderWithScope B(Inst, builderContext);
               auto NewI = B.createCheckedCastBranch(
                  Loc, false /*isExact*/, MI,
                  Inst->getTargetLoweredType().getObjectType(),
                  Inst->getTargetFormalType(),
                  SuccessBB, FailureBB, Inst->getTrueBBCount(),
                  Inst->getFalseBBCount());
               SuccessBB->createPhiArgument(Dest->getType().getObjectType(),
                                            ValueOwnershipKind::Owned);
               B.setInsertionPoint(SuccessBB->begin());
               // Store the result
               B.createStore(Loc, SuccessBB->getArgument(0), Dest,
                             StoreOwnershipQualifier::Unqualified);
               eraseInstAction(Inst);
               return NewI;
            }
         }
      }
   }
   return nullptr;
}

PILInstruction *CastOptimizer::optimizeCheckedCastValueBranchInst(
   CheckedCastValueBranchInst *Inst) {
   // TODO
   return nullptr;
}

PILInstruction *
CastOptimizer::optimizeCheckedCastBranchInst(CheckedCastBranchInst *Inst) {
   if (Inst->isExact())
      return nullptr;

   // InstOptUtils.helper we use to simplify replacing a checked_cast_branch with
   // an optimized checked cast branch.
   auto replaceCastHelper = [](PILBuilderWithScope &B,
                               PILDynamicCastInst dynamicCast,
                               MetatypeInst *mi) -> PILInstruction * {
      // Make sure that the failure block has the new metatype type for
      // its default argument as required when we are in ossa
      // mode. Without ossa, failure blocks do not have args, so we do
      // not need to do anything.
      auto *fBlock = dynamicCast.getFailureBlock();
      if (B.hasOwnership()) {
         fBlock->replacePhiArgumentAndReplaceAllUses(0, mi->getType(),
                                                     ValueOwnershipKind::None);
      }
      return B.createCheckedCastBranch(
         dynamicCast.getLocation(), false /*isExact*/, mi,
         dynamicCast.getTargetLoweredType(),
         dynamicCast.getTargetFormalType(),
         dynamicCast.getSuccessBlock(),
         fBlock, *dynamicCast.getSuccessBlockCount(),
         *dynamicCast.getFailureBlockCount());
   };

   PILDynamicCastInst dynamicCast(Inst);

   auto Op = dynamicCast.getSource();

   // Try to simplify checked_cond_br instructions using existential
   // metatypes by propagating a concrete type whenever it can be
   // determined statically.

   // %0 = metatype $A.Type
   // %1 = init_existential_metatype ..., %0: $A
   // checked_cast_br %1, ....
   // ->
   // %0 = metatype $A.Type
   // checked_cast_br %0 to ...
   if (auto *IEMI = dyn_cast<InitExistentialMetatypeInst>(Op)) {
      if (auto *MI = dyn_cast<MetatypeInst>(IEMI->getOperand())) {
         PILBuilderWithScope B(Inst, builderContext);
         auto *NewI = replaceCastHelper(B, dynamicCast, MI);
         eraseInstAction(Inst);
         return NewI;
      }
   }

   if (auto *EMI = dyn_cast<ExistentialMetatypeInst>(Op)) {
      // Operand of the existential_metatype instruction.
      auto Op = EMI->getOperand();
      auto EmiTy = EMI->getType();

      // %0 = alloc_stack $T
      // %1 = init_existential_addr %0: $*T, $A
      // %2 = existential_metatype $T.Type, %0: $*T
      // checked_cast_br %2 to ...
      // ->
      // %1 = metatype $A.Type
      // checked_cast_br %1 to ...

      if (auto *ASI = dyn_cast<AllocStackInst>(Op)) {
         // Should be in the same BB.
         if (ASI->getParent() != EMI->getParent())
            return nullptr;
         // Check if this alloc_stack is only initialized once by means of
         // single init_existential_addr.
         bool isLegal = true;
         // init_existential instruction used to initialize this alloc_stack.
         InitExistentialAddrInst *FoundIEI = nullptr;
         for (auto Use : getNonDebugUses(ASI)) {
            auto *User = Use->getUser();
            if (isa<ExistentialMetatypeInst>(User) || isa<DestroyAddrInst>(User) ||
                isa<DeallocStackInst>(User))
               continue;
            if (auto *IEI = dyn_cast<InitExistentialAddrInst>(User)) {
               if (!FoundIEI) {
                  FoundIEI = IEI;
                  continue;
               }
            }
            isLegal = false;
            break;
         }

         if (isLegal && FoundIEI) {
            // Should be in the same BB.
            if (FoundIEI->getParent() != EMI->getParent())
               return nullptr;
            // Get the type used to initialize the existential.
            auto LoweredConcreteTy = FoundIEI->getLoweredConcreteType();
            // We don't know enough at compile time about existential
            // and generic type parameters.
            if (LoweredConcreteTy.isAnyExistentialType() ||
                LoweredConcreteTy.is<ArchetypeType>())
               return nullptr;
            // Get the metatype of this type.
            auto EMT = EmiTy.castTo<AnyMetatypeType>();
            auto *MetaTy = MetatypeType::get(LoweredConcreteTy.getAstType(),
                                             EMT->getRepresentation());
            auto CanMetaTy = CanTypeWrapper<MetatypeType>(MetaTy);
            auto PILMetaTy = PILType::getPrimitiveObjectType(CanMetaTy);
            PILBuilderWithScope B(Inst, builderContext);
            B.getOpenedArchetypes().addOpenedArchetypeOperands(
               FoundIEI->getTypeDependentOperands());
            auto *MI = B.createMetatype(FoundIEI->getLoc(), PILMetaTy);
            auto *NewI = replaceCastHelper(B, dynamicCast, MI);
            eraseInstAction(Inst);
            return NewI;
         }
      }

      // %0 = alloc_ref $A
      // %1 = init_existential_ref %0: $A, $...
      // %2 = existential_metatype ..., %1 :  ...
      // checked_cast_br %2, ....
      // ->
      // %1 = metatype $A.Type
      // checked_cast_br %1, ....
      if (auto *FoundIERI = dyn_cast<InitExistentialRefInst>(Op)) {
         auto *ASRI = dyn_cast<AllocRefInst>(FoundIERI->getOperand());
         if (!ASRI)
            return nullptr;
         // Should be in the same BB.
         if (ASRI->getParent() != EMI->getParent())
            return nullptr;
         // Check if this alloc_stack is only initialized once by means of
         // a single init_existential_ref.
         bool isLegal = true;
         for (auto Use : getNonDebugUses(ASRI)) {
            auto *User = Use->getUser();
            if (isa<ExistentialMetatypeInst>(User) || isa<StrongReleaseInst>(User))
               continue;
            if (auto *IERI = dyn_cast<InitExistentialRefInst>(User)) {
               if (IERI == FoundIERI) {
                  continue;
               }
            }
            isLegal = false;
            break;
         }

         if (isLegal && FoundIERI) {
            // Should be in the same BB.
            if (FoundIERI->getParent() != EMI->getParent())
               return nullptr;
            // Get the type used to initialize the existential.
            auto ConcreteTy = FoundIERI->getFormalConcreteType();
            // We don't know enough at compile time about existential
            // and generic type parameters.
            if (ConcreteTy.isAnyExistentialType() ||
                ConcreteTy->is<ArchetypeType>())
               return nullptr;
            // Get the PIL metatype of this type.
            auto EMT = EMI->getType().castTo<AnyMetatypeType>();
            auto *MetaTy = MetatypeType::get(ConcreteTy, EMT->getRepresentation());
            auto CanMetaTy = CanTypeWrapper<MetatypeType>(MetaTy);
            auto PILMetaTy = PILType::getPrimitiveObjectType(CanMetaTy);
            PILBuilderWithScope B(Inst, builderContext);
            B.getOpenedArchetypes().addOpenedArchetypeOperands(
               FoundIERI->getTypeDependentOperands());
            auto *MI = B.createMetatype(FoundIERI->getLoc(), PILMetaTy);
            auto *NewI = replaceCastHelper(B, dynamicCast, MI);
            eraseInstAction(Inst);
            return NewI;
         }
      }
   }

   return nullptr;
}

ValueBase *CastOptimizer::optimizeUnconditionalCheckedCastInst(
   UnconditionalCheckedCastInst *Inst) {
   PILDynamicCastInst dynamicCast(Inst);
   auto Loc = dynamicCast.getLocation();

   // Check if we can statically predict the outcome of the cast.
   auto Feasibility =
      dynamicCast.classifyFeasibility(false /*allowWholeModule*/);

   if (Feasibility == DynamicCastFeasibility::WillFail) {
      // Remove the cast and insert a trap, followed by an
      // unreachable instruction.
      PILBuilderWithScope Builder(Inst, builderContext);
      auto *Trap = Builder.createBuiltinTrap(Loc);
      Inst->replaceAllUsesWithUndef();
      eraseInstAction(Inst);
      Builder.setInsertionPoint(std::next(PILBasicBlock::iterator(Trap)));
      auto *UnreachableInst =
         Builder.createUnreachable(ArtificialUnreachableLocation());

      // Delete everything after the unreachable except for dealloc_stack which we
      // move before the trap.
      deleteInstructionsAfterUnreachable(UnreachableInst, Trap);

      willFailAction();
      return Trap;
   }

   if (Feasibility == DynamicCastFeasibility::WillSucceed) {

      if (Inst->use_empty()) {
         eraseInstAction(Inst);
         willSucceedAction();
         return nullptr;
      }
   }

   PILBuilderWithScope Builder(Inst, builderContext);

   // Try to apply the bridged casts optimizations
   auto NewI = optimizeBridgedCasts(dynamicCast);
   if (NewI) {
      // FIXME: I'm not sure why this is true!
      auto newValue = cast<SingleValueInstruction>(NewI);
      replaceInstUsesAction(Inst, newValue);
      eraseInstAction(Inst);
      willSucceedAction();
      return newValue;
   }

   // If the cast may succeed or fail and can't be optimized into a bridging
   // call, let it be.
   if (Feasibility == DynamicCastFeasibility::MaySucceed) {
      return nullptr;
   }

   assert(Feasibility == DynamicCastFeasibility::WillSucceed);

   if (dynamicCast.isBridgingCast())
      return nullptr;

   auto Result =
      emitSuccessfulScalarUnconditionalCast(Builder, Loc, dynamicCast);

   if (!Result) {
      // No optimization was possible.
      return nullptr;
   }

   replaceInstUsesAction(Inst, Result);
   eraseInstAction(Inst);
   willSucceedAction();
   return Result;
}

/// Deletes all instructions after \p UnreachableInst except dealloc_stack
/// instructions are moved before \p TrapInst.
void CastOptimizer::deleteInstructionsAfterUnreachable(
   PILInstruction *UnreachableInst, PILInstruction *TrapInst) {
   auto UnreachableInstIt = std::next(PILBasicBlock::iterator(UnreachableInst));
   auto *Block = TrapInst->getParent();
   while (UnreachableInstIt != Block->end()) {
      PILInstruction *CurInst = &*UnreachableInstIt;
      ++UnreachableInstIt;
      if (auto *DeallocStack = dyn_cast<DeallocStackInst>(CurInst))
         if (!isa<PILUndef>(DeallocStack->getOperand())) {
            DeallocStack->moveBefore(TrapInst);
            continue;
         }
      CurInst->replaceAllUsesOfAllResultsWithUndef();
      eraseInstAction(CurInst);
   }
}

/// TODO: Move to emitSuccessfulIndirectUnconditionalCast?
///
/// Peephole to avoid runtime calls:
/// unconditional_checked_cast_addr T in %0 : $*T to P in %1 : $*P
/// ->
/// %addr = init_existential_addr %1 : $*P, T
/// copy_addr %0 to %addr
///
/// where T is a type statically known to conform to P.
///
/// In caase P is a class existential type, it generates:
/// %val = load %0 : $*T
/// %existential = init_existential_ref %val : $T, $T, P
/// store %existential to %1 : $*P
///
/// Returns true if the optimization was possible and false otherwise.
static bool optimizeStaticallyKnownInterfaceConformance(
   UnconditionalCheckedCastAddrInst *Inst) {
   auto Loc = Inst->getLoc();
   auto Src = Inst->getSrc();
   auto Dest = Inst->getDest();
   auto SourceType = Inst->getSourceFormalType();
   auto TargetType = Inst->getTargetFormalType();
   auto &Mod = Inst->getModule();

   if (TargetType->isAnyExistentialType() &&
       !SourceType->isAnyExistentialType()) {
      auto &Ctx = Mod.getAstContext();
      auto *SM = Mod.getPolarphpModule();

      auto Proto = dyn_cast<InterfaceDecl>(TargetType->getAnyNominal());
      if (!Proto)
         return false;

      // SourceType is a non-existential type with a non-conditional
      // conformance to a protocol represented by the TargetType.
      //
      // TypeChecker::conformsToInterface checks any conditional conformances. If
      // they depend on information not known until runtime, the conformance
      // will not be returned. For instance, if `X: P` where `T == Int` in `func
      // foo<T>(_: T) { ... X<T>() as? P ... }`, the cast will succeed for
      // `foo(0)` but not for `foo("string")`. There are many cases where
      // everything is completely static (`X<Int>() as? P`), in which case a
      // valid conformance will be returned.
      auto Conformance = SM->conformsToInterface(SourceType, Proto);
      if (Conformance.isInvalid())
         return false;

      PILBuilderWithScope B(Inst);
      SmallVector<InterfaceConformanceRef, 1> NewConformances;
      NewConformances.push_back(Conformance);
      ArrayRef<InterfaceConformanceRef> Conformances =
         Ctx.AllocateCopy(NewConformances);

      auto ExistentialRepr =
         Dest->getType().getPreferredExistentialRepresentation(SourceType);

      switch (ExistentialRepr) {
         default:
            return false;
         case ExistentialRepresentation::Opaque: {
            auto ExistentialAddr = B.createInitExistentialAddr(
               Loc, Dest, SourceType, Src->getType().getObjectType(), Conformances);
            B.createCopyAddr(Loc, Src, ExistentialAddr, IsTake_t::IsTake,
                             IsInitialization_t::IsInitialization);
            break;
         }
         case ExistentialRepresentation::Class: {
            auto Value =
               B.emitLoadValueOperation(Loc, Src, LoadOwnershipQualifier::Take);
            auto Existential =
               B.createInitExistentialRef(Loc, Dest->getType().getObjectType(),
                                          SourceType, Value, Conformances);
            B.emitStoreValueOperation(Loc, Existential, Dest,
                                      StoreOwnershipQualifier::Init);
            break;
         }
         case ExistentialRepresentation::Boxed: {
            auto AllocBox = B.createAllocExistentialBox(Loc, Dest->getType(),
                                                        SourceType, Conformances);
            auto Projection =
               B.createProjectExistentialBox(Loc, Src->getType(), AllocBox);
            // This needs to be a copy_addr (for now) because we must handle
            // address-only types.
            B.createCopyAddr(Loc, Src, Projection, IsTake, IsInitialization);
            B.emitStoreValueOperation(Loc, AllocBox, Dest,
                                      StoreOwnershipQualifier::Init);
            break;
         }
      };
      return true;
   }
   // Not a concrete -> existential cast.
   return false;
}

PILInstruction *CastOptimizer::optimizeUnconditionalCheckedCastAddrInst(
   UnconditionalCheckedCastAddrInst *Inst) {
   PILDynamicCastInst dynamicCast(Inst);
   auto Loc = dynamicCast.getLocation();

   // Check if we can statically predict the outcome of the cast.
   auto Feasibility =
      dynamicCast.classifyFeasibility(false /*allow whole module*/);

   if (Feasibility == DynamicCastFeasibility::MaySucceed) {
      // Forced bridged casts can be still simplified here.
      // If they fail, they fail inside the conversion function.
      if (!dynamicCast.isBridgingCast())
         return nullptr;
   }

   if (Feasibility == DynamicCastFeasibility::WillFail) {
      // Remove the cast and insert a trap, followed by an
      // unreachable instruction.
      PILBuilderWithScope Builder(Inst, builderContext);
      // mem2reg's invariants get unhappy if we don't try to
      // initialize a loadable result.
      if (!dynamicCast.getTargetLoweredType().isAddressOnly(
         Builder.getFunction())) {
         auto undef = PILValue(
            PILUndef::get(dynamicCast.getTargetLoweredType().getObjectType(),
                          Builder.getFunction()));
         Builder.emitStoreValueOperation(Loc, undef, dynamicCast.getDest(),
                                         StoreOwnershipQualifier::Init);
      }
      Builder.emitDestroyAddr(Loc, Inst->getSrc());
      auto *TrapI = Builder.createBuiltinTrap(Loc);
      eraseInstAction(Inst);
      Builder.setInsertionPoint(std::next(TrapI->getIterator()));
      auto *UnreachableInst =
         Builder.createUnreachable(ArtificialUnreachableLocation());

      // Delete everything after the unreachable except for dealloc_stack which we
      // move before the trap.
      deleteInstructionsAfterUnreachable(UnreachableInst, TrapI);

      willFailAction();
   }

   if (Feasibility == DynamicCastFeasibility::WillSucceed ||
       Feasibility == DynamicCastFeasibility::MaySucceed) {

      // Check if a result of a cast is unused. If this is the case, the cast can
      // be removed even if the cast may fail at runtime.
      // Swift optimizer does not claim to be crash-preserving.
      PILValue dest = dynamicCast.getDest();
      bool ResultNotUsed = isa<AllocStackInst>(dest);
      DestroyAddrInst *DestroyDestInst = nullptr;
      if (ResultNotUsed) {
         for (auto Use : dest->getUses()) {
            auto *User = Use->getUser();
            if (isa<DeallocStackInst>(User) || User == Inst)
               continue;
            if (isa<DestroyAddrInst>(User) && !DestroyDestInst) {
               DestroyDestInst = cast<DestroyAddrInst>(User);
               continue;
            }
            ResultNotUsed = false;
            DestroyDestInst = nullptr;
            break;
         }
      }

      if (ResultNotUsed) {
         PILBuilderWithScope B(Inst, builderContext);
         B.createDestroyAddr(Loc, dynamicCast.getSource());
         if (DestroyDestInst)
            eraseInstAction(DestroyDestInst);
         eraseInstAction(Inst);
         willSucceedAction();
         return nullptr;
      }

      // Try to apply the bridged casts optimizations.
      auto NewI = optimizeBridgedCasts(dynamicCast);
      if (NewI) {
         willSucceedAction();
         return nullptr;
      }

      if (Feasibility == DynamicCastFeasibility::MaySucceed)
         return nullptr;

      assert(Feasibility == DynamicCastFeasibility::WillSucceed);

      if (optimizeStaticallyKnownInterfaceConformance(Inst)) {
         eraseInstAction(Inst);
         willSucceedAction();
         return nullptr;
      }

      if (dynamicCast.isBridgingCast())
         return nullptr;

      PILBuilderWithScope Builder(Inst, builderContext);
      if (!emitSuccessfulIndirectUnconditionalCast(Builder, Loc, dynamicCast)) {
         // No optimization was possible.
         return nullptr;
      }

      eraseInstAction(Inst);
      willSucceedAction();
   }

   return nullptr;
}

/// Simplify conversions between thick and objc metatypes.
PILValue CastOptimizer::optimizeMetatypeConversion(
   ConversionInst *mci, MetatypeRepresentation representation) {
   PILValue op = mci->getOperand(0);
   // Instruction has a proper target type already.
   PILType ty = mci->getType();
   auto metatypeTy = op->getType().getAs<AnyMetatypeType>();

   if (metatypeTy->getRepresentation() != representation)
      return PILValue();

   auto loc = mci->getLoc();

   // Rematerialize the incoming metatype instruction with the outgoing type.
   auto replaceCast = [&](PILValue newValue) -> PILValue {
      assert(ty.getAs<AnyMetatypeType>()->getRepresentation() ==
             newValue->getType().getAs<AnyMetatypeType>()->getRepresentation());
      replaceValueUsesAction(mci, newValue);
      eraseInstAction(mci);
      return newValue;
   };

   if (auto *mi = dyn_cast<MetatypeInst>(op)) {
      return replaceCast(
         PILBuilderWithScope(mci, builderContext).createMetatype(loc, ty));
   }

   // For metatype instructions that require an operand, generate the new
   // metatype at the same position as the original to avoid extending the
   // lifetime of `op` past its destroy.
   if (auto *vmi = dyn_cast<ValueMetatypeInst>(op)) {
      return replaceCast(PILBuilderWithScope(vmi, builderContext)
                            .createValueMetatype(loc, ty, vmi->getOperand()));
   }

   if (auto *emi = dyn_cast<ExistentialMetatypeInst>(op)) {
      return replaceCast(
         PILBuilderWithScope(emi, builderContext)
            .createExistentialMetatype(loc, ty, emi->getOperand()));
   }

   return PILValue();
}
